package com.ankie.algorithm;

import java.util.Arrays;

/**
 * @ClassName QuickSort
 * @Author ankie
 * @Date 2020/6/17
 * @Description 快速排序，时间复杂度是 Olog(n)
 *              Arrays.sort()：里面若是常用数据类型就是双轴快排，包装类型就是单轴快排
 */
public class QuickSort {

    private static void quickSort(int[] arr, int leftBound, int rightBound) {
        if (leftBound >= rightBound) {
            return;
        }
        int mid = partition(arr, leftBound, rightBound);
        quickSort(arr, leftBound, mid - 1);
        quickSort(arr, mid + 1, rightBound);
    }

    // 对数组进行分区
    private static int partition(int[] arr, int leftBound, int rightBound) {
        int pivot = arr[rightBound];
        int left = leftBound;
        int right = rightBound - 1;

        while (left <= right) {
            // 找到比最优大的一个值的索引
            while (left <= right && arr[left] < pivot) left++;
            while (left <= right &&  arr[right] > pivot) right--;
            if (left < right) {
                swap(arr, left, right);
            }
        }
        swap(arr, left, rightBound);
        return left;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 66, 29, 50, 48, 27};
        System.out.println(Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
